The Expert System, or Production Rule System, is one of the most important products of recent Artificial Intelligence research Capable of emulating and at times transcending the behavior of human experts in practically any domain, Expert System programs are proving their worth in such diverse areas as medical diagnosis, mineral prospecting, diesel locomotive repair, computer design, organic chemical synthesis, and a host of others. The earliest of such systems, and most of the presently popular ones, have been characterized by a sufficient naivete of knowledge representation that conventional computer architectures were adequate for their execution. With each new insight into the mechanisms of capturing ever more of the complexity and cognitive depth of the human's reasoning processes, such architectures are proving increasingly inadequate if anything approaching real-time speeds of execution are required.
One of the best known Expert System languages is Carnegie Mellon's OPS. This language facilitates approaches to problem solving and knowledge representation and has considerable power. An unfortunate additional characteristic of many OPS systems, particularly those of any real cognitive complexity, is an abysmally low speed of execution on present computers. For example, in complex organic synthesis programs some runs consumed 30 hours of single-user VAX 11/780 time during which approximately 5000 rule firings occurred. The average rule firing rate of 3 per minute is atypically low for Expert Systems, but is representative of figures to be expected for the more complex Expert System programs now being written. It is generally believed that, for effective execution of this next generation of programs, a figure of 1000 firings per second will be required.
In general, the classical hardware approaches to achieving the speed enhancements which the above figures imply have involved the construction of large scale, generalized parallel processing systems (e.g., the CRAY and CYBER), or relatively small serial processors dedicated to the execution of a particular language (e.g., the various LISP machines). For most purposes, the CRAY class machines are far too expensive and, in any case, were they suited to the execution of OPS-like languages, could offer a speed advantage of at best a factor of about 200 with respect to a VAX. A LISP machine, although far less expensive, is not more than a factor of four to eight faster than a VAX, despite the fact that it executes the LISP language in which OPS is written.
On the software side, a popular matching algorithm is the Rete Match Algorithm (see the Forgy and Shepard reference cited below) which exploits common IF parts of production rules and processes these patterns before the system is interpreted. However, this algorithm assumes that few working memory elements change during each cycle (much less than 1%) and is not useful where significant fractions of the working memory elements change in each cycle.
The references listed below teach various types of expert systems and are representative of present day approaches to parallelism for achieving faster execution time. These references are representative of the background of the invention and are incorporated herein by reference.
P. M. Dew "VLSI Architectures For Problems In Numerical Computation", Supercomputers and parallel computation edited by D. J. Paddon, 1984.
Charles L. Forgy and Susan I. Shepard, "Rete: A Fast Matching Algorithm", AI Expert, January 1987.
Dan Neiman, "Adding the Rete Net to your OPS5 Toolbox", AI Expert, January 1987.
Robert J. Douglass, "A Qualitative Assessment of Parallelism in Expert Systems", IEEE Software, May 1985.
Beverly A. Thompson et al, "Inside An Expert System", BYTE, April 1985.
Charles L. Seitz, "The Cosmic Cube", Communications of the ACM, January 1985.
J. R. Gurd et al, "The Manchester Prototype Dataflow Computer", Communications of the ACM, January 1985.
William M. Raike, "The Fifth Generation in Japan", BYTE, April 1985.
Michael F. Deering, "Architectures for AI", BYTE, April 1985.
Robert H. Michaelsen et al, "The Technology of Expert Systems", BYTE, April 1985.
Patrick H. Winston, "The LISP Revolution", BYTE, April 1985.
Charles Forgy et al, "Initial Assessment of Architectures for Production Systems", Proceedings of the American Association of Artificial Intelligence, pp. 116-112, August 1984.
J. H. Griesmer et al, "WES/MVS: A Continuous Real Time Expert System", Proceedings of the American Association of Artificial Intelligence, pp. 130-136, August 1984.
Salvatore J. Stolfo, "Five Parallel Algorithms for Production System Execution On the Dado Machine", Proceedings of the American Association of Artificial Intelligence, pp. 300-307, August 1984.